#include <stdio.h>
#include <stdlib.h>

#define INIT_SIZE 10  // 初始表的大小
#define INCREMENT 5   // 每次扩容的增量

// 定义顺序表结构体
typedef struct {
    int *data;     // 指向存储数据的数组的指针
    int length;    // 当前顺序表的长度
    int capacity;  // 当前顺序表的容量
} SeqList;

// 初始化顺序表
void InitSeqList(SeqList *list) {
    list->data = (int *)malloc(INIT_SIZE * sizeof(int));  // 初始分配内存
    if (list->data == NULL) {
        fprintf(stderr, "内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    list->length = 0;        // 初始长度为0
    list->capacity = INIT_SIZE;  // 初始容量为INIT_SIZE
}

// 扩展顺序表容量
void IncreaseCapacity(SeqList *list) {
    int *new_data = (int *)realloc(list->data, (list->capacity + INCREMENT) * sizeof(int));
    if (new_data == NULL) {
        fprintf(stderr, "内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    list->data = new_data;
    list->capacity += INCREMENT;
}

// 在指定位置插入元素
void Insert(SeqList *list, int index, int value) {
    if (index < 0 || index > list->length) {
        fprintf(stderr, "插入位置错误\n");
        return;
    }
    
    // 如果空间不足，先扩展容量
    if (list->length >= list->capacity) {
        IncreaseCapacity(list);
    }
    
    // 后移元素腾出位置
    for (int i = list->length - 1; i >= index; --i) {
        list->data[i + 1] = list->data[i];
    }
    
    // 插入新元素
    list->data[index] = value;
    ++list->length;
}

// 删除指定位置的元素
void Delete(SeqList *list, int index) {
    if (index < 0 || index >= list->length) {
        fprintf(stderr, "删除位置错误\n");
        return;
    }
    
    // 前移元素覆盖被删除元素
    for (int i = index; i < list->length - 1; ++i) {
        list->data[i] = list->data[i + 1];
    }
    
    --list->length;
}

// 获取指定位置的元素
int Get(SeqList *list, int index) {
    if (index < 0 || index >= list->length) {
        fprintf(stderr, "获取位置错误\n");
        exit(EXIT_FAILURE);
    }
    return list->data[index];
}

// 打印顺序表中的所有元素
void Print(SeqList *list) {
    printf("顺序表中的元素为：");
    for (int i = 0; i < list->length; ++i) {
        printf("%d ", list->data[i]);
    }
    printf("\n");
}

// 释放顺序表占用的动态内存
void Destroy(SeqList *list) {
    free(list->data);
    list->data = NULL;
    list->length = 0;
    list->capacity = 0;
}

int main() {
    SeqList list;
    InitSeqList(&list);

    // 插入一些元素
    Insert(&list, 0, 10);
    Insert(&list, 1, 20);
    Insert(&list, 2, 30);
    Insert(&list, 1, 15);

    // 打印顺序表
    Print(&list);

    // 删除元素
    Delete(&list, 1);

    // 打印删除后的顺序表
    Print(&list);

    // 获取指定位置的元素
    printf("位置1的元素为：%d\n", Get(&list, 1));

    // 释放动态内存
    Destroy(&list);

    return 0;
}
